SP1811 LCS - Longest Common Substring

一道后缀自动机的板题。

我们从根结点开始匹配，如果有转移就将$cnt++$

不然就顺着后缀链接向上跳，直到找到有转移的点，用 $Maxlen$ 继续匹配。(后缀链接一定是它的子串，也能被匹配)。

如果没有跳到合适的点就从根重新匹配。

最后选取最大的$cnt$就可以了。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 2 * 250000 , MAXC = 26;
struct Suffix_Automaton {
	int Size , Last , Maxlen[ MAXN + 5 ];
	int Trans[ MAXN + 5 ][ MAXC + 5 ] , Link[ MAXN + 5 ];
	
	Suffix_Automaton( ) { Size = Last = 1; }
	
	void Copy( int u , int v ) {
		for( int i = 1 ; i <= MAXC ; i ++ )
			Trans[ u ][ i ] = Trans[ v ][ i ];
	}
	void Extend( int chr ) {
		int Newnode = ++ Size , u = Last;
		Maxlen[ Newnode ] = Maxlen[ u ] + 1;
		
		for( ; u && !Trans[ u ][ chr ] ; u = Link[ u ] )
			Trans[ u ][ chr ] = Newnode;
		
		if( !u ) Link[ Newnode ] = 1;
		else {
			int v = Trans[ u ][ chr ];
			
			if( Maxlen[ v ] == Maxlen[ u ] + 1 ) Link[ Newnode ] = v;
			else {
				int w = ++ Size;
				Copy( w , v ); Maxlen[ w ] = Maxlen[ u ] + 1;
				for( ; u && Trans[ u ][ chr ] == v ; u = Link[ u ] ) Trans[ u ][ chr ] = w;
				Link[ w ] = Link[ v ];
				Link[ v ] = Link[ Newnode ] = w;	
			}
		}
		Last = Newnode;
	}
	
	void Build( char *str ) {
		int len = strlen( str );
		for( int i = 0 ; i < len ; i ++ )
			Extend( str[ i ] - 'a' + 1 );
	}
	int Calc( char *str ) {
		int len = strlen( str );
		int Ans = 0 , tot = 0 , u = 1;
		for( int i = 0 ; i < len ; i ++ ) {
			int chr = str[ i ] - 'a' + 1;
			if( Trans[ u ][ chr ] ) {
				tot ++;
				u = Trans[ u ][ chr ];
			}
			else {
				for( ; u && !Trans[ u ][ chr ] ; u = Link[ u ] );
				if( !u ) tot = 0 , u = 1;
				else {
					tot = Maxlen[ u ] + 1;
					u = Trans[ u ][ chr ];
				}
			}
			Ans = max( Ans , tot ); 
		}
		return Ans;
	}
}SAM;

char str[ 3 ][ MAXN + 5 ];
int main( ) {
	for( int i = 1 ; i <= 2 ; i ++ )
		scanf("%s",str[ i ]);
	SAM.Build( str[ 1 ] );
	printf("%d", SAM.Calc( str[ 2 ] ) );
	return 0;
}